home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000119_icon-group-sender _Wed Dec 15 20:12:49 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  2KB
  1. Received: by cheltenham.cs.arizona.edu; Wed, 15 Dec 1993 18:26:48 MST
  2. Date: 15 Dec 93 20:12:49 GMT
  3. From: agate!howland.reston.ans.net!news.moneng.mei.com!uwm.edu!fnnews.fnal.gov!fnalv.fnal.gov!mglass@ucbvax.Berkeley.EDU
  4. Organization: Fermi National Accelerator Lab
  5. Subject: Powersets and every x:=!S insert(S...
  6. Message-Id: <1993Dec15.141249.1@fnalo.fnal.gov>
  7. Sender: icon-group-request@cs.arizona.edu
  8. To: icon-group@cs.arizona.edu
  9. Status: R
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12.  
  13.      May I jump in and combine two recent threads?  Specifically,
  14. the recent question about how to compute a powerset intersects
  15. with the long discussion of "every x := !S do insert(S, ...)."
  16.  
  17.      One cool way to compute a powerset, given a set S, is:
  18.  
  19.         ps := set([set()])
  20.         every insert(ps, set([!S]) ++ !copy(ps))
  21.  
  22.      This should be, I believe, a fairly convincing example of why
  23. even a rigorous programmer might occasionally write a statement of
  24. the form:
  25.  
  26.         "every x := !ps do insert(ps, ...)"
  27.  
  28.      It was suggested that using copy() will clean up the problem
  29. with such constructions, as it did above.  If icon sets behaved
  30. like real sets, the following might work:
  31.  
  32.         * every insert(ps, set([!S]) ++ !ps)
  33.  
  34.      However one can hardly recommend such a practice!  Suppose
  35. you were computing for example, the products of all the subsets,
  36. instead of the subsets themselves.  Without invoking copy(), the
  37. following might not work:
  38.  
  39.         products := set([1])
  40.         every insert(products, !S * !copy(products)) 
  41.  
  42.      An amusing side-note is the illusion that the "++" set union
  43. operator is not commutative!  In my example
  44.  
  45.         !copy(ps) ++ set([!S])
  46.  
  47. is not the same as
  48.  
  49.         set([!S]) ++ !copy(ps)
  50.  
  51.      It is this apparent non-commutative behavior--really order of
  52. generation and evaluation--which bugged my original construction,
  53. which was to compute the powerset by successively _deleting_ elements:
  54.  
  55.         * ps := set(S)
  56.         * every insert(ps, !copy(ps) -- set([!S]))
  57.  
  58.      Enough!
  59.  
  60. -- Michael Glass                 |  Practice random acts of
  61.    mglass@fnalv.fnal.gov         |  humor and senseless mirth.
  62.